#include <string.h>
#include <iostream>
using namespace std;

class Element;

void Swap(Element* first, Element* second);
char ConvertToUpper(char ch);
char ConvertToLower(char ch);

class Element
{
public:

/**
* CONSTRUCTORS
*/
	Element()
	{
		m_data = NULL;
		m_nextElement = NULL;
		m_previousElement = NULL;
	}
	Element(const char* data)
	: m_data(NULL)
	, m_nextElement(NULL)
	, m_previousElement(NULL)
	{
		m_data = new char[strlen(data) + 1];
		strcpy(m_data, data);
	}

/**
* DESTRUCTOR
*/
	~Element()
	{
		delete[] m_data;
		m_data = NULL;

		m_nextElement = NULL;
		m_previousElement = NULL;
	}

/**
* DESCRIPTION	: Appends a new element at the end of the list.
* ARGUMENTS		: New Element to insert.
* RETURN VALUE	: None.
*/
	void Append(Element& newElement)
	{
		Element* temp = this;
		while(temp->m_nextElement)
		{
			temp = temp->m_nextElement;
		}
		temp->m_nextElement = new Element(newElement.GetData());
		temp->m_nextElement->m_previousElement = temp;
	}

/**
* DESCRIPTION	: Returns the first element of the list.
* ARGUMENTS		: None.
* RETURN VALUE	: First element of the list.
*/
	Element* First()
	{
		Element* temp = this;
		while(temp->m_previousElement)
		{
			temp = temp->m_previousElement;
		}
		return temp;
	}

/**
* DESCRIPTION	: Returns the last element of the list.
* ARGUMENTS		: None.
* RETURN VALUE	: Last element of the list.
*/
	Element* Last()
	{
		Element* temp = this;
		while(temp->m_nextElement)
		{
			temp = temp->m_nextElement;
		}
		return temp;
	}

/**
* DESCRIPTION	: Prints the elements of the list to console output.
* ARGUMENTS		: Integer value 0 means print the complete list, any other value will just print that element's content.
* RETURN VALUE	: First element of the list.
* CONDIERATION	: Specifying zero as the default value, as it is not mentioned what default value should be used as argument
*/
	void Print(unsigned int count = 1)
	{
		if(count == 0)
		{
			//Traverse to the root element
			Element* temp = First();
			while(temp->m_nextElement)
			{
				cout << '[' << temp->GetData() << ']' << "->";
				temp = temp->m_nextElement;
			}
			cout << '[' << temp->GetData() << ']' << endl;
		}
		else
		{
			cout << '[' << m_data << ']' << endl;
		}
	}

/**
* DESCRIPTION	: Returns the string data of the element.
* ARGUMENTS		: None.
* RETURN VALUE	: Character pointer to the string data.
*/
	char* GetData() { return m_data; }
/**
* DESCRIPTION	: Returns the previous element.
* ARGUMENTS		: None.
* RETURN VALUE	: Pointer to the previous element.
*/
	Element* Previous() { return m_previousElement; }
/**
* DESCRIPTION	: Returns the next element.
* ARGUMENTS		: None.
* RETURN VALUE	: Pointer to the next element.
*/
	Element* Next() { return m_nextElement; }

/**
* DESCRIPTION	: Returns the nth element.
* ARGUMENTS		: Index of the nth element.
* RETURN VALUE	: Pointer to the nth element.
*/
	Element* Nth(const int index)
	{
		//Traverse to the root
		Element* temp = First();
		Element* searchResult = NULL;
		int count = 0;
		while(count <= index)
		{
			if(count == index)
			{
				searchResult = temp;
				break;
			}
			if(!temp->m_nextElement)
			{
				break;
			}
			temp = temp->m_nextElement;
			++count;
		}

		return searchResult;
	}

/**
* DESCRIPTION	: Inserts a new element to the list.
* ARGUMENTS		: Reference of the new element to be inserted.
* RETURN VALUE	: Pointer first element of the list.
* CONSIDERATION	: In the requirements it is not mentioned what should be the return value of this function.
*/
	Element* Insert(Element& newElement)
	{
		m_previousElement->m_nextElement = new Element(newElement.GetData());
		m_previousElement->m_nextElement->m_previousElement = m_previousElement;
		m_previousElement->m_nextElement->m_nextElement = this;
		m_previousElement = m_previousElement->m_nextElement;

		return First();
	}

/**
* DESCRIPTION	: Inserts a new list to the list.
* ARGUMENTS		: Reference of the any element of the new list to be inserted.
* RETURN VALUE	: Pointer first element of the list.
* CONSIDERATION	: In the requirements it is not mentioned what should be the return value of this function.
*/
	Element* Insert(Element* newList)
	{
		m_previousElement->m_nextElement = newList->First();
		newList->First()->m_previousElement = m_previousElement;
		m_previousElement = newList->Last();
		newList->Last()->m_nextElement = this;

		return First();
	}

/**
* DESCRIPTION	: Removes this element from the list.
* ARGUMENTS		: None.
* RETURN VALUE	: Pointer first element of the list.
* CONSIDERATION	: In the requirements it is not mentioned what should be the return value of this function.
*/
	Element* Remove()
	{
		if(m_previousElement)
			m_previousElement->m_nextElement = m_nextElement;
		if(m_nextElement)
			m_nextElement->m_previousElement = m_previousElement;

		return First();
	}

/**
* DESCRIPTION	: Removes all elements from the current till the end of the list.
* ARGUMENTS		: None.
* RETURN VALUE	: None.
*/
	void TearDown()
	{
		Element* temp = Last();
		while(temp != this)
		{
			Element* prevElement = temp->m_previousElement;
			temp->Remove();
			delete temp;
			temp = prevElement;
		}
		this->Remove();
		delete this;
	}

/**
* DESCRIPTION	: Searches a list linearly for a string.
* ARGUMENTS		: Reference of the string to be searched.
* RETURN VALUE	: Found element.
* CONSIDERATION	: If there are two elements of the same string value in the list, then this will return the first element found only.
*/
	Element* BruteSearch(const char* searchVal)
	{
		Element* prev = this, *nxt = this;
		while(prev)
		{
			if(!strcmp(searchVal, prev->GetData()))
			{
				return prev;
			}
			prev = prev->m_previousElement;
		}
		while(nxt)
		{
			if(!strcmp(searchVal, nxt->GetData()))
			{
				return nxt;
			}
			nxt = nxt->m_nextElement;
		}
		return NULL;
	}

/**
* DESCRIPTION	: Set a new data to the element.
* ARGUMENTS		: Reference of the string data to be set.
* RETURN VALUE	: None.
* CONSIDERATION	: If there are two elements of the same string value in the list, then this will return the first element found only.
*/
	void SetNewData(char* newData) 
	{
		if(m_data)
			delete m_data;
		m_data = new char[strlen(newData) + 1];
		strcpy(m_data, newData); 
	}

/**
* DESCRIPTION	: Sorts the list alphabetically.
* ARGUMENTS		: None.
* RETURN VALUE	: First Element of the new sorted list.
* CONSIDERATION	: This sort will not consider case sensitivity
*/
	Element* Sort()
	{
		Element* temp = First();
		while(temp->m_nextElement)
		{
			Element* nxt = temp->m_nextElement;
			while(nxt)
			{
				//Convert both strings to lower case just for comparison
				char* firstData = new char[strlen(temp->GetData()) + 1];
				strcpy(firstData, temp->GetData());
				char* travel = firstData;
				while(*travel != '\0')
				{
					*travel = ConvertToLower(*travel);
					++travel;
				}
				char* secondData = new char[strlen(nxt->GetData()) + 1];
				strcpy(secondData, nxt->GetData());
				travel = secondData;
				while(*travel != '\0')
				{
					*travel = ConvertToLower(*travel);
					++travel;
				}
				//Compare the converted strings
				if(strcoll(firstData, secondData) > 0)
				{
					Swap(temp, nxt);
				}
				nxt = nxt->m_nextElement;

				//delete the temporary allocations
				delete[] firstData;
				delete[] secondData;
			}
			temp = temp->m_nextElement;
		}
		return First();
	}

/**
* DESCRIPTION	: Counts the number of elements in the list.
* ARGUMENTS		: None.
* RETURN VALUE	: Number of elements in the list.
*/
	unsigned int Count()
	{
		unsigned int count = 0;
		Element* temp = First();
		while(temp)
		{
			++count;
			temp = temp->m_nextElement;
		}
		return count;
	}

/**
* DESCRIPTION	: Sorts the list alphabetically.
* ARGUMENTS		: None.
* RETURN VALUE	: First Element of the new sorted list.
* CONSIDERATION	: This search will not consider case sensitivity
*/
	Element* BinarySearch(const char* searchVal)
	{
		Element* searchResult = NULL;
		unsigned int count = Count();
		int midValue = count / 2;
		int first = 0, last = count - 1;
		while(last > first)
		{
			//Convert both strings to lower case just for comparison
			char* firstData = new char[strlen(Nth(midValue)->GetData()) + 1];
			strcpy(firstData, Nth(midValue)->GetData());
			char* travel = firstData;
			while(*travel != '\0')
			{
				*travel = ConvertToLower(*travel);
				++travel;
			}
			char* secondData = new char[strlen(searchVal) + 1];
			strcpy(secondData, searchVal);
			travel = secondData;
			while(*travel != '\0')
			{
				*travel = ConvertToLower(*travel);
				++travel;
			}

			//Compare Result and recaluculate first, last and mid values
			int result = strcoll(secondData, firstData);
			if(result < 0)
			{
				//First becomes mid val
				last = midValue;
				//mid val recalculated
				midValue = first + ((last - first + 1) / 2);
			}
			else if(result > 0)
			{
				//Last becomes mid val
				first = midValue;
				//mid val recalculated
				midValue = first + ((last - first + 1) / 2);
			}
			else
			{
				//result found
				searchResult = Nth(midValue);

				//Delete the temp data and then break from the loop
				delete[] firstData;
				delete[] secondData;
				break;
			}

			delete[] firstData;
			delete[] secondData;
		}

		return searchResult;
	}

private:
/**
* DESCRIPTION	: Pointer to the string data for the element.
*/
	char* m_data;
/**
* DESCRIPTION	: Pointer to the next element in the list.
*/
	Element* m_nextElement;
/**
* DESCRIPTION	: Pointer to the previous element in the list.
*/
	Element* m_previousElement;
};

/**
* DESCRIPTION	: Swaps the string values of two Elements
* ARGUMENTS		: First Element	: Second Element
* RETURN VALUE	: None.
*/
void Swap(Element* first, Element* second)
{
	char* firstData = new char[strlen(first->GetData()) + 1];
	strcpy(firstData, first->GetData());
	first->SetNewData(second->GetData());
	second->SetNewData(firstData);

	delete[] firstData;
}

/**
* DESCRIPTION	: Converts a character to upper case
* ARGUMENTS		: Character to convert.
* RETURN VALUE	: Converted character.
*/
char ConvertToUpper(char ch)
{
    if (ch < 'a' || ch > 'z') 
	{
            return ch;
    }
    return ch - ('a' - 'A');
}

/**
* DESCRIPTION	: Converts a character to lower case
* ARGUMENTS		: Character to convert.
* RETURN VALUE	: Converted character.
*/
char ConvertToLower(char ch) 
{
    if (ch < 'A' || ch > 'Z') 
	{
            return ch;
    }
    return ch + ('a' - 'A');
}

void TestFunction()
{
	// construct a list
	Element *root = new Element("Hello");

	root->Append(Element("World"));
	root->Append(Element("This"));
	root->Append(Element("Is"));
	root->Append(Element("a"));
	root->Append(Element("Linked"));
	root->Append(Element("List"));
	root->Append(Element("of"));
	root->Append(Element("Strings"));

	root->Print(0);

	// test finding nodes
	Element *nth = root->Nth(3);
/**
* MODIFICATION TO THE TEST CODE
*/
	if(nth)
	{
		//If nth element searched doesnt exist then all the calls following this without if(nth) check will fail
		nth->Print(1);
		nth->Previous()->Print(1);
		nth->Next()->Print(1);
		nth->First()->Print(1);
		nth->Last()->Print(1);
	}

	// test appending and inserting 
	nth->Append(Element("."));
	nth->Last()->Print();

	root = nth->Insert(Element("Definitely"));
	root->Print(0);

	Element *secondList = new Element("Second");
	secondList->Append(Element("List"));

	root = nth->Insert(secondList->Last());
	root->Print(0);

	root = nth->Remove();
	delete nth;
	root->Print(0);

	// check brute, sort and binary search

	Element *found = root->BruteSearch("of");
	found->Print();

	found = root->BinarySearch("List");
	if (found) // the list is not sorted yet so BinarySearch may fail
	{ 
		found->Print();
	}

	root = root->Sort();
	root->Print(0);

	found = root->BinarySearch("List");
/**
* MODIFICATION TO THE TEST CODE
*/
	//found->Print();//If the searched string is not found this call will cause a crash
	if(found)
		found->Print();

	// tear down
	root->Nth(5)->TearDown();
	root->Print(0);
	root->TearDown();
}

int main()
{
	TestFunction();
	return 0;
}

/*
[Hello]->[World]->[This]->[Is]->[a]->[Linked]->[List]->[of]->[Strings]
[Is]
[This]
[a]
[Hello]
[Strings]
[.]
[Hello]->[World]->[This]->[Definitely]->[Is]->[a]->[Linked]->[List]->[of]->[Strings]->[.]
[Hello]->[World]->[This]->[Definitely]->[Second]->[List]->[Is]->[a]->[Linked]->[List]->[of]->[Strings]->[.]
[Hello]->[World]->[This]->[Definitely]->[Second]->[List]->[a]->[Linked]->[List]->[of]->[Strings]->[.]
[of]
[List]
[.]->[a]->[Definitely]->[Hello]->[Linked]->[List]->[List]->[of]->[Second]->[Strings]->[This]->[World]
[List]
[.]->[a]->[Definitely]->[Hello]->[Linked]
*/
